package com.dyz.leetcode;

import java.util.ArrayList;
import java.util.List;

public class IsValidBST98 {
    //二叉搜索树中序遍历 是一个递增的序列
    List<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        //先中序便利存入数组中
        minOrder(root);
        //取第一个也是最小的一个
        int pre = list.get(0);
        for(int i=1; i<list.size(); i++){
            if(pre<list.get(i)){
                pre = list.get(i);
            }else {
                return false;
            }
        }
        return true;
    }
    private void minOrder(TreeNode root){
        if(root==null){return;}
        minOrder(root.left);
        list.add(root.val);
        minOrder(root.right);
    }
    //在inorder减枝
    public boolean isValidBST1(TreeNode root) {
        return inorder(root, Long.MIN_VALUE, Long.MAX_VALUE);

    }
    private boolean inorder(TreeNode root, long min, long max){
        if(root==null){return true;}
        boolean leftboolean = inorder(root.left, min, (long)(root.val));
        if(min>=root.val || root.val>=max){return false;}
        boolean rightboolean = inorder(root.right, (long)(root.val), max);
        return rightboolean && leftboolean;
    }
}
